from tools_algorithm import *


class Solution:
    def valueAfterKSeconds(self, n: int, k: int) -> int:
        mod = 1000000007
        a = [1] * n
        for _ in range(k):
            for i in range(1, n):
                a[i] += a[i - 1]
                a[i] %= mod
        return a[-1]


s = Solution()
print(s.valueAfterKSeconds(10, 10))

from sortedcontainers import SortedSet


class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues.sort()
        st = set([0])
        ans = 0
        for v in rewardValues:
            nst = set()
            nst.update(st)
            for s in st:
                if v > s:
                    ans = max(ans, v + s)
                    if v + s < 2001:
                        nst.add(v + s)
            st = nst

        return ans


s = Solution()
print(s.maxTotalReward([1, 1, 3, 3]))
